package com.example.leetcode.DFS;

/**
 *
 * 题目描述
 * 给定一个二维的 0-1 矩阵，如果第 (i, j) 位置是 1，则表示第 i 个人和第 j 个人是朋友。已知
 * 朋友关系是可以传递的，即如果 a 是 b 的朋友，b 是 c 的朋友，那么 a 和 c 也是朋友，换言之这
 * 三个人处于同一个朋友圈之内。求一共有多少个朋友圈。
 * 输入输出样例
 * 输入是一个二维数组，输出是一个整数，表示朋友圈数量。因为朋友关系具有对称性，该二
 * 维数组为对称矩阵。同时，因为自己是自己的朋友，对角线上的值全部为 1。
 * Input:
 * [[1,1,0],
 * [1,1,0],
 * [0,0,1]]
 * Output: 2
 * 在这个样例中，[1,2] 处于一个朋友圈，[3] 处于一个朋友圈。
 *
 * 其实这个是图转为了邻接矩阵，把这个邻接矩阵转为图：
 * 0 —— 1
 * 2
 *
 * @ClassName Solution547
 * @Description TODO
 * @Author liuzhihui
 * @Date 4/5/2021 下午 6:23
 * @Version 1.0
 **/
public class Solution_2_547 {
    public  int findCircleNum(int[][] isConnected) {
        // 获取图的元素个数
        int length = isConnected.length;
        // 标记图的当前元素是否被访问过
        boolean[] visitded= new boolean[isConnected.length];
        // 结果集
        int count = 0;

        //遍历图
        for (int i = 0; i < length; i++) {
            // 判断当前城市时候访问过
            if (!visitded[i]){
                // 寻找当前城市与那些城市相连
                dfs(isConnected, length, visitded, i);
                count++;
            }
        }
        return count;
    }
    private  void dfs(int[][] isConnected, int length, boolean[] visitded, int i) {
        //寻找与城市i直接或间接相连的城市
        for (int j = 0; j < length; j++) {
            //城市i与城市j相连 并且 城市j没有被访问过
            if (isConnected[i][j] == 1 && !visitded[j]){
                visitded[j] =true;
                dfs(isConnected, length, visitded, j);
            }
        }
    }

    //------------------------------------------------------------------------------------
    // 练习
    public int findCircleNum1(int[][] isConnected){
        // 获取图中的元素个数
        int length = isConnected.length;
        // 标记图中的元素是否被访问过
        boolean[] visited = new boolean[length];
        int result = 0;
        // 遍历图
        for (int i = 0; i < length; i++) {
            if (!visited[i]){
                dfs1(isConnected, i, visited);
                result++;
            }
        }
        return result;
    }
    private void dfs1(int[][] isConnected, int i, boolean[] visited) {
        for (int j = 0; j < isConnected.length; j++) {
            if (!visited[j] && isConnected[i][j] == 1){
                visited[j] = true;
                dfs1(isConnected,j,visited);
            }
        }
    }

}
